The present invention relates generally to communication systems, and more particularly to reducing multicast forwarding states in a multicast communication system.
In today""s information age, communication networks are often used for transporting information from an information provider to one or more information consumers. One technique for transporting information from an information provider to a group of information consumers over the communication network is known as xe2x80x9cmulticasting.xe2x80x9d Multicasting allows the information provider (referred to hereinafter as a xe2x80x9cmulticast sourcexe2x80x9d) to transmit a single unit of multicast information (referred to hereinafter as a xe2x80x9cmulticast packetxe2x80x9d) simultaneously to all information consumers (referred to hereinafter individually as a xe2x80x9cmulticast clientxe2x80x9d and collectively as xe2x80x9cmulticast clientsxe2x80x9d) in the multicast group, specifically by addressing the multicast packet to the multicast group using a multicast address. The multicast clients monitor the communication network for multicast packets addressed to the multicast group.
In order to distribute multicast packets from a particular multicast source S to the multicast clients for a particular multicast group G, the multicast packet is routed through a number of multicast routers. For convenience, the path through the various multicast routers is referred to as the xe2x80x9cmulticast distribution treexe2x80x9d for the (S,G) pair. The multicast routers utilize various multicast routing protocols, such as Multicast Open Shortest-Path First (MOSPF), Distance Vector Multicast Routing Protocol (DVMRP), Protocol Independent Multicast (PIM), or Multicast Border Gateway Protocol (MBGP), in order to determine the multicast distribution tree for the (S,G) pair.
More specifically, a router runs multicast routing protocols in order to determine multicast routing information. The router maintains the multicast routing information in a routing table called a Multicast Routing Information Base (MRIB). The DVMRP routing table and the-MBGP routing table are examples of a MRIB. For multicast routing protocols such as MOSPF and PIM that do not inherently utilize a multicast routing table, the unicast routing table is used as the MRIB. Each interface may have a separate MRIB.
Using the multicast routing information in the MRIB(s), the router sets up multicast forwarding states that define how the router forwards multicast packets. These multicast forwarding states are maintained by a Multicast Table Manager (MTM) in a multicast forwarding table. Each multicast forwarding entry in the multicast forwarding table corresponds to a particular (S,G) pair, and defines the inbound and outbound interfaces for the (S,G) pair.
Some multicast routing protocols, such as PIM, allow the router to forward multicast packets from any multicast source to a particular multicast group G. Such a multicast forwarding state is designated a (*,G) forwarding state. As with any other (S,G) pair, the MTM maintains a multicast forwarding entry for the (*,G) forwarding state. For convenience, a multicast forwarding entry for the (*,G) state is referred to hereinafter as a xe2x80x9cdefaultxe2x80x9d multicast forwarding entry, while other multicast forwarding entries are referred to hereinafter as xe2x80x9cnon-defaultxe2x80x9d multicast forwarding entries.
Each multicast forwarding entry includes, among other things, an inbound list indicating the accepted (preferred) and rejected inbound interfaces for the (S,G) pair and an outbound list indicating the outbound interfaces for the (S,G) pair. If a particular (S,G) pair has multiple accepted (preferred) inbound interfaces, particularly due to different multicast routing protocols running on different interfaces, the MTM determines a most-preferred inbound interface from among the accepted (preferred) inbound interfaces. In order to support certain multicast routing protocols, such as PIM, each outbound interface in the outbound list may be associated with a source list indicating the multicast sources that are associated with the outbound interface.
When the router receives a multicast packet for (S,G) from a particular interface, the router searches the multicast forwarding table for a corresponding multicast forwarding entry and processes the multicast packet accordingly. In a typical multicast communication network, it is common for a multicast forwarding table to have a large number of multicast forwarding entries. The large number of multicast forwarding entries makes the multicast forwarding table very large, and also makes searching the multicast forwarding table for the multicast forwarding entry a relatively time-consuming operation.
Thus, a need has remained for a technique that reduces the number of multicast forwarding states in a multicast routing device, and more particularly for a technique that reduces the number of multicast forwarding entries in the multicast forwarding table.
In accordance with one aspect of the invention, forwarding states are maintained in such a way that all non-default forwarding states are non-overlapping.
In accordance with another aspect of the invention, a prefix is assigned to each forwarding state. The source address S and the prefix together define the source address range for the forwarding state. The prefix is assigned in such a way that the source address range defined by S/prefix does not overlap with the source address ranges of any other non-default forwarding state.
In accordance with yet another aspect of the invention, a non-overlapping prefix is determined by finding an enclosing range for S (the matching range) that contains a number of more-specific enclosing ranges, where each enclosing range is characterized by a lower boundary and an upper boundary; determining a maximum upper boundary within the matching range that is less than or equal to S; determining a minimum lower boundary within the matching range that is greater than or equal to S; and determining the minimum prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to the maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to the minimum lower boundary.
In accordance with still another aspect of the invention, a the source address range of a fowarding state is adjusted when a new route is detected or an existing route changes or is aged.